//
// Created by 86188 on 2022/9/15.
//

#ifndef SORTPROJECT_USUALSEARCH_H
#define SORTPROJECT_USUALSEARCH_H

typedef int ElemType;

typedef struct {    // 查找表的数据结构
    ElemType *elem; // 元素存储空间的基址，建表时按实际长度分配，0号单元留空
    int TableLen;   // 表的长度
} SSTable,SeqList;

/**
 * 顺序查找
 * @param ST
 * @param key
 * @return
 */
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0] = key;   // 哨兵结点
    int i;
    for (i = ST.TableLen; ST.elem[i]!=key ; --i);   // 从后往前查找
    return i;   // 若表中不存在关键字为key的元素，将查到i为0时退出for循环
}

/**
 * 折半查找(二分查找)
 * @param L
 * @param key
 * @return
 */
int Binary_Search(SeqList L,ElemType key){
    int low = 0;
    int high = L.TableLen-1;
    int mid;
    while (low<=high){
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid] > key)
            low = mid+1;
        else
            high = mid - 1;
    }
    return -1;
}


#endif //SORTPROJECT_USUALSEARCH_H
